R Setup and Required Packages
In the following code chunk we load the packages used to support our analysis.
# check if packages are not installed; if yes, install missing packages
packages = c("tidyverse", "magrittr", # typical data analysis packages
"MALDIquant", # match closest points between two vectors
"foreach", "parallel", # packages used for parallelizing some code chunks
"R.matlab")
newPackages = packages[!(packages %in% installed.packages()[,"Package"])]
if(length(newPackages) > 0) install.packages(newPackages)
# using the library command to load all packages; invisible used to avoid printing all packages and dependencies used
invisible(lapply(packages, library, character.only = TRUE))
# source("./Functions.R") # our custom built functions
# set.seed(2020)
# startTime <- Sys.time()
Gait Acceleration Data and Rational Subgroups
We converted the raw IMU acceleration signals in the local to the global reference frame and removed the gravity. The acceleration signals were then transformed back to the local reference frame. Sagittal acceleration, lateral acceleration, and acceleration magnitude signals were then calculated. We used the vertical acceleration component to segment the gait cycles in order to isolate individual gait cycles. The acceleration profiles along with the experimental time stamps were stored in mat files.
In this code chunk we load the segmented acceleration mat files. The \(1^{st}\) 10 minutes of the data were considered as warm up period and thus excluded form the analysis. The acceleration profiles of the gait cycles during each walking cycle were grouped into a rational subgroup. We stored the start and end times of the walking cycles in csv files and loaded and used them in the following code chunk. The acceleration profiles within each start and end times to subgroup the gait cycles.
for (id in setdiff(1:15, 13)) {
#################### Read start and end time of the subgroups
video <- read.csv(paste0(file="../Data/csvFiles/Sub", id, ".csv"))
video_leave <- video$Leaves
video_leave <- video_leave[!is.na(video_leave)]
video_leave <- video_leave - 600
video_leave <- video_leave[video_leave > 0]
video_enter <- video$Enters
video_enter <- video_enter[!is.na(video_enter)]
video_enter <- video_enter - 600
video_enter <- video_enter[video_enter > 0]
################################################### Read from mat files
raw1 <- readMat(paste0("../Data/matFiles/Subject", id, "_aZ_seg.mat"))
raw2 <- raw1$gait
num_rows <- length(raw2)/5
aM <- list("vector")
aS <- list("vector")
aL <- list("vector")
exp_time <- c()
for (i in 1:num_rows) {
aM[[i]] <- raw2[[1*num_rows + i]][[1]][1,]
aS[[i]] <- raw2[[2*num_rows + i]][[1]][1,]
aL[[i]] <- raw2[[3*num_rows + i]][[1]][1,]
exp_time[i] <- raw2[[i+4*num_rows]][[1]][1,1]
}
###################################################### Create subgroups
if (video_leave[1] > video_enter[1]){
video_leave <- c(exp_time[1], video_leave)
}
if (tail(video_leave, 1) > tail(video_enter, 1)){
video_enter <- c(video_enter, tail(exp_time, 1))
}
conf <- 0.05 * mean(video_enter - video_leave) # 5% confidence for each subgroup
# Match video subroup times against the experimental times from mat files
leave_index <- match.closest(video_leave + conf, exp_time)
enter_index <- match.closest(video_enter - conf, exp_time)
aM_list <- list()
aS_list <- list()
aL_list <- list()
t_list <- list()
for (i in 1:length(leave_index)) {
aM_list[[i]] <- aM[leave_index[i]:enter_index[i]]
aS_list[[i]] <- aS[leave_index[i]:enter_index[i]]
aL_list[[i]] <- aL[leave_index[i]:enter_index[i]]
t_list[[i]] <- exp_time[leave_index[i]:enter_index[i]]
}
len <- c()
for (i in 1:length(aM_list)) {
len <- c(len, lengths(aM_list[[i]]))
}
cut_len <- quantile(len, 0.02)
for (i in 1:length(aM_list)) {
remove_ind <- which(lengths(aM_list[[i]]) < cut_len)
remove_ind <- c(remove_ind, 3000)
aM_list[[i]] <- aM_list[[i]][-remove_ind]
aS_list[[i]] <- aS_list[[i]][-remove_ind]
aL_list[[i]] <- aL_list[[i]][-remove_ind]
t_list[[i]] <- t_list[[i]][-remove_ind]
}
batchSize <- lengths(aM_list)
###############################################
aM_list_all <- do.call(c, aM_list)
aS_list_all <- do.call(c, aS_list)
aL_list_all <- do.call(c, aL_list)
t_all <- do.call(c, t_list)
###############################################
aM_mat <- do.call(rbind, aM_list_all)[,1:cut_len]
aS_mat <- do.call(rbind, aS_list_all)[,1:cut_len]
aL_mat <- do.call(rbind, aL_list_all)[,1:cut_len]
##################
assign(paste0("sub", id, "_aMSLT"),
list(aMag=aM_mat, aSag=aS_mat, aLat=aL_mat, time=t_all, batchSize=batchSize))
}
########################################### Save
save(sub1_aMSLT, sub2_aMSLT, sub3_aMSLT, sub4_aMSLT, sub5_aMSLT, sub6_aMSLT,
sub7_aMSLT, sub8_aMSLT, sub9_aMSLT, sub10_aMSLT, sub11_aMSLT, sub12_aMSLT,
sub14_aMSLT, sub15_aMSLT,
file="../Data/rData/subGs_for_depth.Rdata")
Depth Calculation
Explain about depth concept in general; centrality and outlyingness
Mode Depth
Calculate mode depth…
load(file="../Data/rData/subGs_for_depth.Rdata")
cores = detectCores() - 2 # to give the server some breathing Room
cl = makePSOCKcluster(cores)
registerDoParallel(cl)
for (id in setdiff(1:15, 13)) {
aMag <- get(paste0("sub", id, "_aMSLT"))$aMag
tExp <- get(paste0("sub", id, "_aMSLT"))$time
################################## Mode Depth
inControl <- aMag[1:500,]
inControlDepth <- {depth.mode(fdata(inControl))}$dep
###################### foreach
onlineDepth <- c()
end <- nrow(aMag)
onlineDepth <- foreach(i=501:end, .packages = c('fda.usc', 'tidyverse'),
.combine='c') %dopar% {
temp1 <- aMag %>% .[i,]
append1 <- rbind(inControl, temp1)
temp2 <- depth.mode(fdata(append1))
temp3 <- temp2$dep %>% .[501]
temp3
}
modeDepth <- c(inControlDepth, onlineDepth)
assign(paste0("sub", id, "_mode_mag"),
list(modeDepth=modeDepth, tExp=tExp))
}
save(sub1_mode_mag, sub2_mode_mag, sub3_mode_mag, sub4_mode_mag, sub5_mode_mag, sub6_mode_mag,
sub7_mode_mag, sub8_mode_mag, sub9_mode_mag, sub10_mode_mag, sub11_mode_mag, sub12_mode_mag,
sub14_mode_mag, sub15_mode_mag,
file="../Data/rData/mode_mag.Rdata")
MFHD Depth
Calculate MFHD depth…
Explain since it take very long it was performed on supercomputer cluster in parallel and the eval option in the following code chunk was set to false since this could take weeks to run on the local computer.
#################################################
load(file="../Data/rData/subGs_for_depth.Rdata")
cores = detectCores() - 2 # to give the server some breathing Room
cl = makePSOCKcluster(cores)
registerDoParallel(cl)
for (id in setdiff(1:15, 13)) {
aSag <- get(paste0("sub", id, "_aMSLT"))$aSag
aLat <- get(paste0("sub", id, "_aMSLT"))$aLat
tExp <- get(paste0("sub", id, "_aMSLT"))$time
################################## Mode Depth
inControlSag <- aSag[1:500,]
inControlLat <- aLat[1:500,]
inControlDepth <- {MFHD(y1=inControlSag, y2=inControlLat, alpha=0.125, Beta=0.5)}$MFHDdepth[1,]
###################### foreach
onlineDepth <- c()
end <- nrow(aSag)
onlineDepth <- foreach(i=501:end, .packages = c('fda.usc', 'tidyverse', 'MFHD'),
.combine='c') %dopar% {
temp1 <- aSag %>% .[i,]
temp2 <- aLat %>% .[i,]
append1 <- rbind(inControlSag, temp1)
append2 <- rbind(inControlLat, temp2)
temp3 <- MFHD(y1=append1, y2=append2, alpha=0.125, Beta=0.5)
temp4 <- temp3$MFHDdepth %>% .[1,501]
temp4
}
MFHDdepth <- c(inControlDepth, onlineDepth)
assign(paste0("sub", id, "_MFHD"),
list(MFHDdepth=MFHDdepth, tExp=tExp))
}
save(sub1_MFHD, sub2_MFHD, sub3_MFHD, sub4_MFHD, sub5_MFHD, sub6_MFHD, sub7_MFHD, sub8_MFHD,
sub9_MFHD, sub10_MFHD, sub11_MFHD, sub12_MFHD, sub14_MFHD, sub15_MFHD,
file="../Data/rData/MFHD.Rdata")
Visualize the MFHD Depth
load(file="../Data/rData/MFHD.Rdata")
for (id in setdiff(1:15, 13)) {
dep <- get(paste0("sub", id, "_MFHD"))$MFHDdepth
t <- get(paste0("sub", id, "_MFHD"))$tExp
cat("###", paste0("Subject", id), "{-}",'\n')
plot(t, dep, pch=16, cex=1,col=c(rep("red", 500), rep("black", length(dep)-500)))
legend("topright", legend=c("Baseline data", "New data"), col=c("red", "black"),
pch=16)
cat('\n \n')
}
Subject1

Subject2

Subject3

Subject4

Subject5

Subject6

Subject7

Subject8

Subject9

Subject10

Subject11

Subject12

Subject14

Subject15

References
LS0tDQp0aXRsZTogIkEgcGVyc29uYWxpemVkIGFuZCBub24tcGFyYW1ldHJpYyBmcmFtZXdvcmsgZm9yIGRldGVjdGluZyBjaGFuZ2VzIGluIGdhaXQgY3ljbGVzIg0KYXV0aG9yOg0KICAtIG5hbWU6ICJTYWViIFJhZ2FuaSBMYW1vb2tpIF5bRW1haWw6IHNhZWJyYWdhQGJ1ZmZhbG8uZWR1IHwgV2Vic2l0ZTogPGEgaHJlZj1cImh0dHBzOi8vd3d3LmxpbmtlZGluLmNvbS9pbi9zYWViLXJhZ2FuaS1sYW1vb2tpLTEyM2E5NjU4L1wiPkxpbmtlZEluPC9hPl0iDQogICAgYWZmaWxpYXRpb246IERlcGFydG1lbnQgb2YgTWVjaGFuaWNhbCAmIEFlcm9zcGFjZSBFbmdpbmVlcmluZywgVW5pdmVyc2l0eSBhdCBCdWZmYWxvDQogIC0gbmFtZTogIkppeWVvbiBLYW5nIF5bRW1haWw6IGppeWVvbmtAYnVmZmFsby5lZHUgfCBQaG9uZTogKzEtNzE2LTY0NS02MDYzIHwgV2Vic2l0ZTogPGEgaHJlZj1cImh0dHA6Ly9lbmdpbmVlcmluZy5idWZmYWxvLmVkdS9pbmR1c3RyaWFsLXN5c3RlbXMvcGVvcGxlL2ZhY3VsdHktZGlyZWN0b3J5L2otamFuZy5odG1sXCI+VW5pdmVyc2l0eSBhdCBCdWZmYWxvIE9mZmljaWFsPC9hPl0iDQogICAgYWZmaWxpYXRpb246IERlcGFydG1lbnQgb2YgTWVjaGFuaWNhbCAmIEFlcm9zcGFjZSBFbmdpbmVlcmluZywgVW5pdmVyc2l0eSBhdCBCdWZmYWxvDQogIC0gbmFtZTogIkxvcmEgQS4gQ2F2dW90byBeW0VtYWlsOiBsb3JhY2F2dUBidWZmYWxvLmVkdSB8IFBob25lOiArMS03MTYtNjQ1LTQ2OTYgfCBXZWJzaXRlOiA8YSBocmVmPVwiaHR0cDovL2VuZ2luZWVyaW5nLmJ1ZmZhbG8uZWR1L2luZHVzdHJpYWwtc3lzdGVtcy9wZW9wbGUvZmFjdWx0eS1kaXJlY3RvcnkvY2F2dW90by1sb3JhLmh0bWxcIj5Vbml2ZXJzaXR5IGF0IEJ1ZmZhbG8gT2ZmaWNpYWw8L2E+XSINCiAgICBhZmZpbGlhdGlvbjogRGVwYXJ0bWVudCBvZiBJbmR1c3RyaWFsIGFuZCBTeXN0ZW1zIEVuZ2luZWVyaW5nLCBVbml2ZXJzaXR5IGF0IEJ1ZmZhbG8NCiAgLSBuYW1lOiAiRmFkZWwgTS4gTWVnYWhlZCBeW0VtYWlsOiBmbWVnYWhlZEBtaWFtaW9oLmVkdSB8IFBob25lOiArMS01MTMtNTI5LTQxODUgfCBXZWJzaXRlOiA8YSBocmVmPVwiaHR0cHM6Ly9taWFtaW9oLmVkdS9mc2IvZGlyZWN0b3J5Lz91cD0vZGlyZWN0b3J5L21lZ2FoZWZtXCI+TWlhbWkgVW5pdmVyc2l0eSBPZmZpY2lhbDwvYT5dIg0KICAgIGFmZmlsaWF0aW9uOiBGYXJtZXIgU2Nob29sIG9mIEJ1c2luZXNzLCBNaWFtaSBVbml2ZXJzaXR5DQogIC0gbmFtZTogIkFsbGlzb24gSm9uZXMgRmFybWVyIF5bRW1haWw6IGZhcm1lcmwyQG1pYW1pb2guZWR1IHwgUGhvbmU6ICsxLTUxMy01MjktNDgyMyB8IFdlYnNpdGU6IDxhIGhyZWY9XCJodHRwczovL21pYW1pb2guZWR1L2ZzYi9kaXJlY3RvcnkvP3VwPS9kaXJlY3RvcnkvZmFybWVybDJcIj5NaWFtaSBVbml2ZXJzaXR5IE9mZmljaWFsPC9hPl0iDQogICAgYWZmaWxpYXRpb246IEZhcm1lciBTY2hvb2wgb2YgQnVzaW5lc3MsIE1pYW1pIFVuaXZlcnNpdHkNCmJpYmxpb2dyYXBoeTogRVdNQVJlZnMuYmliDQpjc2w6IGFwYS5jc2wNCmRhdGU6ICJgciBmb3JtYXQoU3lzLnRpbWUoKSwgJyVCICVkLCAlWScpYCINCm91dHB1dDogDQogIGh0bWxfZG9jdW1lbnQ6DQogICAgdG9jOiBUUlVFDQogICAgdG9jX2Zsb2F0OiBUUlVFDQogICAgbnVtYmVyX3NlY3Rpb25zOiBUUlVFDQogICAgdGhlbWU6IHNpbXBsZXgNCiAgICBwYWdlZF9kZjogVFJVRQ0KICAgIGNvZGVfZm9sZGluZzogc2hvdw0KICAgIGNvZGVfZG93bmxvYWQ6IFRSVUUNCiAgaW5jbHVkZXM6DQogICAgaW5faGVhZGVyOiBzdHJ1Y3R1cmUudGV4DQotLS0NCg0KDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFLA0KICAgICAgICAgICAgICAgICAgICAgIHdhcm5pbmcgPSBGQUxTRSwNCiAgICAgICAgICAgICAgICAgICAgICBtZXNzYWdlID0gRkFMU0UsDQogICAgICAgICAgICAgICAgICAgICAgY2FjaGUgPSBUUlVFLA0KICAgICAgICAgICAgICAgICAgICAgIHByb2dyZXNzID0gRkFMU0UsIA0KICAgICAgICAgICAgICAgICAgICAgIHZlcmJvc2UgPSBGQUxTRSwNCiAgICAgICAgICAgICAgICAgICAgICBkcGkgPSA2MDApDQpvcHRpb25zKHF3cmFwczJfbWFya3VwID0gIm1hcmtkb3duIikNCg0KDQpgYGANCg0KLS0tDQoNCiMgUiBTZXR1cCBhbmQgUmVxdWlyZWQgUGFja2FnZXMNCg0KSW4gdGhlIGZvbGxvd2luZyBjb2RlIGNodW5rIHdlIGxvYWQgdGhlIHBhY2thZ2VzIHVzZWQgdG8gc3VwcG9ydCBvdXIgYW5hbHlzaXMuICANCg0KYGBge3IgcGFja2FnZXMsIGNhY2hlPUZBTFNFfQ0KDQojIGNoZWNrIGlmIHBhY2thZ2VzIGFyZSBub3QgaW5zdGFsbGVkOyBpZiB5ZXMsIGluc3RhbGwgbWlzc2luZyBwYWNrYWdlcw0KcGFja2FnZXMgPSBjKCJ0aWR5dmVyc2UiLCAibWFncml0dHIiLCAjIHR5cGljYWwgZGF0YSBhbmFseXNpcyBwYWNrYWdlcw0KICAgICAgICAgICAgICJNQUxESXF1YW50IiwgIyBtYXRjaCBjbG9zZXN0IHBvaW50cyBiZXR3ZWVuIHR3byB2ZWN0b3JzDQogICAgICAgICAgICAgImZvcmVhY2giLCAicGFyYWxsZWwiLCAjIHBhY2thZ2VzIHVzZWQgZm9yIHBhcmFsbGVsaXppbmcgc29tZSBjb2RlIGNodW5rcw0KICAgICAgICAgICAgICJSLm1hdGxhYiIpDQpuZXdQYWNrYWdlcyA9IHBhY2thZ2VzWyEocGFja2FnZXMgJWluJSBpbnN0YWxsZWQucGFja2FnZXMoKVssIlBhY2thZ2UiXSldDQppZihsZW5ndGgobmV3UGFja2FnZXMpID4gMCkgaW5zdGFsbC5wYWNrYWdlcyhuZXdQYWNrYWdlcykNCg0KIyB1c2luZyB0aGUgbGlicmFyeSBjb21tYW5kIHRvIGxvYWQgYWxsIHBhY2thZ2VzOyBpbnZpc2libGUgdXNlZCB0byBhdm9pZCBwcmludGluZyBhbGwgcGFja2FnZXMgYW5kIGRlcGVuZGVuY2llcyB1c2VkDQppbnZpc2libGUobGFwcGx5KHBhY2thZ2VzLCBsaWJyYXJ5LCBjaGFyYWN0ZXIub25seSA9IFRSVUUpKQ0KDQojIHNvdXJjZSgiLi9GdW5jdGlvbnMuUiIpICMgb3VyIGN1c3RvbSBidWlsdCBmdW5jdGlvbnMNCg0KIyBzZXQuc2VlZCgyMDIwKQ0KIyBzdGFydFRpbWUgPC0gU3lzLnRpbWUoKQ0KYGBgDQoNCg0KLS0tDQoNCiMgR2FpdCBBY2NlbGVyYXRpb24gRGF0YSBhbmQgUmF0aW9uYWwgU3ViZ3JvdXBzDQoNCldlIGNvbnZlcnRlZCB0aGUgcmF3IElNVSBhY2NlbGVyYXRpb24gc2lnbmFscyBpbiB0aGUgbG9jYWwgdG8gdGhlIGdsb2JhbCByZWZlcmVuY2UgZnJhbWUgYW5kIHJlbW92ZWQgdGhlIGdyYXZpdHkuIFRoZSBhY2NlbGVyYXRpb24gc2lnbmFscyB3ZXJlIHRoZW4gdHJhbnNmb3JtZWQgYmFjayB0byB0aGUgbG9jYWwgcmVmZXJlbmNlIGZyYW1lLiBTYWdpdHRhbCBhY2NlbGVyYXRpb24sIGxhdGVyYWwgYWNjZWxlcmF0aW9uLCBhbmQgYWNjZWxlcmF0aW9uIG1hZ25pdHVkZSBzaWduYWxzIHdlcmUgdGhlbiBjYWxjdWxhdGVkLiBXZSB1c2VkIHRoZSB2ZXJ0aWNhbCBhY2NlbGVyYXRpb24gY29tcG9uZW50IHRvIHNlZ21lbnQgdGhlIGdhaXQgY3ljbGVzIGluIG9yZGVyIHRvIGlzb2xhdGUgaW5kaXZpZHVhbCBnYWl0IGN5Y2xlcy4gVGhlIGFjY2VsZXJhdGlvbiBwcm9maWxlcyBhbG9uZyB3aXRoIHRoZSBleHBlcmltZW50YWwgdGltZSBzdGFtcHMgd2VyZSBzdG9yZWQgaW4gbWF0IGZpbGVzLg0KDQpJbiB0aGlzIGNvZGUgY2h1bmsgd2UgbG9hZCB0aGUgc2VnbWVudGVkIGFjY2VsZXJhdGlvbiBtYXQgZmlsZXMuIFRoZSAkMV57c3R9JCAxMCBtaW51dGVzIG9mIHRoZSBkYXRhIHdlcmUgY29uc2lkZXJlZCBhcyB3YXJtIHVwIHBlcmlvZCBhbmQgdGh1cyBleGNsdWRlZCBmb3JtIHRoZSBhbmFseXNpcy4gVGhlIGFjY2VsZXJhdGlvbiBwcm9maWxlcyBvZiB0aGUgZ2FpdCBjeWNsZXMgZHVyaW5nIGVhY2ggd2Fsa2luZyBjeWNsZSB3ZXJlIGdyb3VwZWQgaW50byBhIHJhdGlvbmFsIHN1Ymdyb3VwLiBXZSBzdG9yZWQgdGhlIHN0YXJ0IGFuZCBlbmQgdGltZXMgb2YgdGhlIHdhbGtpbmcgY3ljbGVzIGluIGNzdiBmaWxlcyBhbmQgbG9hZGVkIGFuZCB1c2VkIHRoZW0gaW4gdGhlIGZvbGxvd2luZyBjb2RlIGNodW5rLiBUaGUgYWNjZWxlcmF0aW9uIHByb2ZpbGVzIHdpdGhpbiBlYWNoIHN0YXJ0IGFuZCBlbmQgdGltZXMgdG8gc3ViZ3JvdXAgdGhlIGdhaXQgY3ljbGVzLg0KDQoNCmBgYHtyIHJlYWQtc3ViZ30NCg0KZm9yIChpZCBpbiBzZXRkaWZmKDE6MTUsIDEzKSkgew0KICAjIyMjIyMjIyMjIyMjIyMjIyMjIyBSZWFkIHN0YXJ0IGFuZCBlbmQgdGltZSBvZiB0aGUgc3ViZ3JvdXBzDQogIHZpZGVvIDwtIHJlYWQuY3N2KHBhc3RlMChmaWxlPSIuLi9EYXRhL2NzdkZpbGVzL1N1YiIsIGlkLCAiLmNzdiIpKQ0KDQogIHZpZGVvX2xlYXZlIDwtIHZpZGVvJExlYXZlcw0KICB2aWRlb19sZWF2ZSA8LSB2aWRlb19sZWF2ZVshaXMubmEodmlkZW9fbGVhdmUpXQ0KICB2aWRlb19sZWF2ZSA8LSB2aWRlb19sZWF2ZSAtIDYwMA0KICB2aWRlb19sZWF2ZSA8LSB2aWRlb19sZWF2ZVt2aWRlb19sZWF2ZSA+IDBdDQoNCiAgdmlkZW9fZW50ZXIgPC0gdmlkZW8kRW50ZXJzDQogIHZpZGVvX2VudGVyIDwtIHZpZGVvX2VudGVyWyFpcy5uYSh2aWRlb19lbnRlcildDQogIHZpZGVvX2VudGVyIDwtIHZpZGVvX2VudGVyIC0gNjAwDQogIHZpZGVvX2VudGVyIDwtIHZpZGVvX2VudGVyW3ZpZGVvX2VudGVyID4gMF0NCg0KICAjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMgUmVhZCBmcm9tIG1hdCBmaWxlcw0KICByYXcxIDwtIHJlYWRNYXQocGFzdGUwKCIuLi9EYXRhL21hdEZpbGVzL1N1YmplY3QiLCBpZCwgIl9hWl9zZWcubWF0IikpDQoNCiAgcmF3MiA8LSByYXcxJGdhaXQNCg0KICBudW1fcm93cyA8LSBsZW5ndGgocmF3MikvNQ0KDQogIGFNIDwtIGxpc3QoInZlY3RvciIpDQogIGFTIDwtIGxpc3QoInZlY3RvciIpDQogIGFMIDwtIGxpc3QoInZlY3RvciIpDQogIGV4cF90aW1lIDwtIGMoKQ0KICBmb3IgKGkgaW4gMTpudW1fcm93cykgew0KICAgIGFNW1tpXV0gPC0gcmF3MltbMSpudW1fcm93cyArIGldXVtbMV1dWzEsXQ0KICAgIGFTW1tpXV0gPC0gcmF3MltbMipudW1fcm93cyArIGldXVtbMV1dWzEsXQ0KICAgIGFMW1tpXV0gPC0gcmF3MltbMypudW1fcm93cyArIGldXVtbMV1dWzEsXQ0KICAgIGV4cF90aW1lW2ldIDwtIHJhdzJbW2krNCpudW1fcm93c11dW1sxXV1bMSwxXQ0KICB9DQoNCiAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIENyZWF0ZSBzdWJncm91cHMNCiAgaWYgKHZpZGVvX2xlYXZlWzFdID4gdmlkZW9fZW50ZXJbMV0pew0KICAgIHZpZGVvX2xlYXZlIDwtIGMoZXhwX3RpbWVbMV0sIHZpZGVvX2xlYXZlKQ0KICB9DQoNCiAgaWYgKHRhaWwodmlkZW9fbGVhdmUsIDEpID4gdGFpbCh2aWRlb19lbnRlciwgMSkpew0KICAgIHZpZGVvX2VudGVyIDwtIGModmlkZW9fZW50ZXIsIHRhaWwoZXhwX3RpbWUsIDEpKQ0KICB9DQoNCiAgY29uZiA8LSAwLjA1ICogbWVhbih2aWRlb19lbnRlciAtIHZpZGVvX2xlYXZlKSAjIDUlIGNvbmZpZGVuY2UgZm9yIGVhY2ggc3ViZ3JvdXANCg0KICAjIE1hdGNoIHZpZGVvIHN1YnJvdXAgdGltZXMgYWdhaW5zdCB0aGUgZXhwZXJpbWVudGFsIHRpbWVzIGZyb20gbWF0IGZpbGVzDQogIGxlYXZlX2luZGV4IDwtIG1hdGNoLmNsb3Nlc3QodmlkZW9fbGVhdmUgKyBjb25mLCBleHBfdGltZSkNCiAgZW50ZXJfaW5kZXggPC0gbWF0Y2guY2xvc2VzdCh2aWRlb19lbnRlciAtIGNvbmYsIGV4cF90aW1lKQ0KDQogIGFNX2xpc3QgPC0gbGlzdCgpDQogIGFTX2xpc3QgPC0gbGlzdCgpDQogIGFMX2xpc3QgPC0gbGlzdCgpDQogIHRfbGlzdCA8LSBsaXN0KCkNCiAgZm9yIChpIGluIDE6bGVuZ3RoKGxlYXZlX2luZGV4KSkgew0KICAgIGFNX2xpc3RbW2ldXSA8LSBhTVtsZWF2ZV9pbmRleFtpXTplbnRlcl9pbmRleFtpXV0NCiAgICBhU19saXN0W1tpXV0gPC0gYVNbbGVhdmVfaW5kZXhbaV06ZW50ZXJfaW5kZXhbaV1dDQogICAgYUxfbGlzdFtbaV1dIDwtIGFMW2xlYXZlX2luZGV4W2ldOmVudGVyX2luZGV4W2ldXQ0KICAgIHRfbGlzdFtbaV1dIDwtIGV4cF90aW1lW2xlYXZlX2luZGV4W2ldOmVudGVyX2luZGV4W2ldXQ0KICB9DQoNCiAgbGVuIDwtIGMoKQ0KICBmb3IgKGkgaW4gMTpsZW5ndGgoYU1fbGlzdCkpIHsNCiAgICBsZW4gPC0gYyhsZW4sIGxlbmd0aHMoYU1fbGlzdFtbaV1dKSkNCiAgfQ0KDQogIGN1dF9sZW4gPC0gcXVhbnRpbGUobGVuLCAwLjAyKQ0KDQogIGZvciAoaSBpbiAxOmxlbmd0aChhTV9saXN0KSkgew0KICAgIHJlbW92ZV9pbmQgPC0gd2hpY2gobGVuZ3RocyhhTV9saXN0W1tpXV0pIDwgY3V0X2xlbikNCiAgICByZW1vdmVfaW5kIDwtIGMocmVtb3ZlX2luZCwgMzAwMCkNCiAgICBhTV9saXN0W1tpXV0gPC0gYU1fbGlzdFtbaV1dWy1yZW1vdmVfaW5kXQ0KICAgIGFTX2xpc3RbW2ldXSA8LSBhU19saXN0W1tpXV1bLXJlbW92ZV9pbmRdDQogICAgYUxfbGlzdFtbaV1dIDwtIGFMX2xpc3RbW2ldXVstcmVtb3ZlX2luZF0NCiAgICB0X2xpc3RbW2ldXSA8LSB0X2xpc3RbW2ldXVstcmVtb3ZlX2luZF0NCiAgfQ0KDQogIGJhdGNoU2l6ZSA8LSBsZW5ndGhzKGFNX2xpc3QpDQoNCiAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCiAgYU1fbGlzdF9hbGwgPC0gZG8uY2FsbChjLCBhTV9saXN0KQ0KICBhU19saXN0X2FsbCA8LSBkby5jYWxsKGMsIGFTX2xpc3QpDQogIGFMX2xpc3RfYWxsIDwtIGRvLmNhbGwoYywgYUxfbGlzdCkNCiAgdF9hbGwgPC0gZG8uY2FsbChjLCB0X2xpc3QpDQogICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQogIGFNX21hdCA8LSBkby5jYWxsKHJiaW5kLCBhTV9saXN0X2FsbClbLDE6Y3V0X2xlbl0NCiAgYVNfbWF0IDwtIGRvLmNhbGwocmJpbmQsIGFTX2xpc3RfYWxsKVssMTpjdXRfbGVuXQ0KICBhTF9tYXQgPC0gZG8uY2FsbChyYmluZCwgYUxfbGlzdF9hbGwpWywxOmN1dF9sZW5dDQoNCiAgIyMjIyMjIyMjIyMjIyMjIyMjDQogIGFzc2lnbihwYXN0ZTAoInN1YiIsIGlkLCAiX2FNU0xUIiksDQogICAgICAgICBsaXN0KGFNYWc9YU1fbWF0LCBhU2FnPWFTX21hdCwgYUxhdD1hTF9tYXQsIHRpbWU9dF9hbGwsIGJhdGNoU2l6ZT1iYXRjaFNpemUpKQ0KfQ0KDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIFNhdmUNCnNhdmUoc3ViMV9hTVNMVCwgc3ViMl9hTVNMVCwgc3ViM19hTVNMVCwgc3ViNF9hTVNMVCwgc3ViNV9hTVNMVCwgc3ViNl9hTVNMVCwNCiAgICAgc3ViN19hTVNMVCwgc3ViOF9hTVNMVCwgc3ViOV9hTVNMVCwgc3ViMTBfYU1TTFQsIHN1YjExX2FNU0xULCBzdWIxMl9hTVNMVCwNCiAgICAgc3ViMTRfYU1TTFQsIHN1YjE1X2FNU0xULA0KDQogICAgIGZpbGU9Ii4uL0RhdGEvckRhdGEvc3ViR3NfZm9yX2RlcHRoLlJkYXRhIikNCmBgYA0KDQoNCiMgRGVwdGggQ2FsY3VsYXRpb24NCg0KRXhwbGFpbiBhYm91dCBkZXB0aCBjb25jZXB0IGluIGdlbmVyYWw7IGNlbnRyYWxpdHkgYW5kIG91dGx5aW5nbmVzcw0KDQojIyBNb2RlIERlcHRoDQoNCkNhbGN1bGF0ZSBtb2RlIGRlcHRoLi4uDQoNCmBgYHtyIG1vZGUtZGVwdGgsIGV2YWw9RkFMU0V9DQoNCmxvYWQoZmlsZT0iLi4vRGF0YS9yRGF0YS9zdWJHc19mb3JfZGVwdGguUmRhdGEiKQ0KDQpjb3JlcyA9IGRldGVjdENvcmVzKCkgLSAyICMgdG8gZ2l2ZSB0aGUgc2VydmVyIHNvbWUgYnJlYXRoaW5nIFJvb20NCmNsID0gbWFrZVBTT0NLY2x1c3Rlcihjb3JlcykNCnJlZ2lzdGVyRG9QYXJhbGxlbChjbCkNCg0KZm9yIChpZCBpbiBzZXRkaWZmKDE6MTUsIDEzKSkgew0KICANCiAgYU1hZyA8LSBnZXQocGFzdGUwKCJzdWIiLCBpZCwgIl9hTVNMVCIpKSRhTWFnDQogIHRFeHAgPC0gZ2V0KHBhc3RlMCgic3ViIiwgaWQsICJfYU1TTFQiKSkkdGltZQ0KICANCiAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyBNb2RlIERlcHRoDQogIGluQ29udHJvbCA8LSBhTWFnWzE6NTAwLF0NCiAgaW5Db250cm9sRGVwdGggPC0ge2RlcHRoLm1vZGUoZmRhdGEoaW5Db250cm9sKSl9JGRlcA0KICANCiAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyBmb3JlYWNoDQogIG9ubGluZURlcHRoIDwtIGMoKQ0KICBlbmQgPC0gbnJvdyhhTWFnKQ0KICBvbmxpbmVEZXB0aCA8LSBmb3JlYWNoKGk9NTAxOmVuZCwgLnBhY2thZ2VzID0gYygnZmRhLnVzYycsICd0aWR5dmVyc2UnKSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAuY29tYmluZT0nYycpICVkb3BhciUgew0KICAgICAgICAgICAgICAgICAgICAgICAgICAgdGVtcDEgPC0gYU1hZyAlPiUgLltpLF0NCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGFwcGVuZDEgPC0gcmJpbmQoaW5Db250cm9sLCB0ZW1wMSkNCiAgICAgICAgICAgICAgICAgICAgICAgICAgIHRlbXAyIDwtIGRlcHRoLm1vZGUoZmRhdGEoYXBwZW5kMSkpDQogICAgICAgICAgICAgICAgICAgICAgICAgICANCiAgICAgICAgICAgICAgICAgICAgICAgICAgIHRlbXAzIDwtIHRlbXAyJGRlcCAlPiUgLls1MDFdDQogICAgICAgICAgICAgICAgICAgICAgICAgICB0ZW1wMw0KICAgICAgICAgICAgICAgICAgICAgICAgIH0NCiAgDQogIG1vZGVEZXB0aCA8LSBjKGluQ29udHJvbERlcHRoLCBvbmxpbmVEZXB0aCkNCiAgDQogIGFzc2lnbihwYXN0ZTAoInN1YiIsIGlkLCAiX21vZGVfbWFnIiksDQogICAgICAgICBsaXN0KG1vZGVEZXB0aD1tb2RlRGVwdGgsIHRFeHA9dEV4cCkpDQp9DQoNCnNhdmUoc3ViMV9tb2RlX21hZywgc3ViMl9tb2RlX21hZywgc3ViM19tb2RlX21hZywgc3ViNF9tb2RlX21hZywgc3ViNV9tb2RlX21hZywgc3ViNl9tb2RlX21hZywNCiAgICAgc3ViN19tb2RlX21hZywgc3ViOF9tb2RlX21hZywgc3ViOV9tb2RlX21hZywgc3ViMTBfbW9kZV9tYWcsIHN1YjExX21vZGVfbWFnLCBzdWIxMl9tb2RlX21hZywNCiAgICAgc3ViMTRfbW9kZV9tYWcsIHN1YjE1X21vZGVfbWFnLA0KICAgICBmaWxlPSIuLi9EYXRhL3JEYXRhL21vZGVfbWFnLlJkYXRhIikNCmBgYA0KDQo8IS0tICMjIFZpc3VhbGl6ZSB0aGUgTW9kZSBEZXB0aCB7LnRhYnNldCAudGFic2V0LWZhZGV9IC0tPg0KDQo8IS0tIGBgYHtyIHZpc19Nb2RlLCBmaWcuYWxpZ249ImNlbnRlciIsIHJlc3VsdHM9ImFzaXMiLCBvdXQud2lkdGg9IjEwMCUifSAtLT4NCg0KPCEtLSBsb2FkKGZpbGU9Ii4uL0RhdGEvckRhdGEvbW9kZV9tYWcuUmRhdGEiKSAtLT4NCg0KPCEtLSBmb3IgKGlkIGluIHNldGRpZmYoMToxNSwgMTMpKSB7IC0tPg0KPCEtLSAgIGRlcCA8LSBnZXQocGFzdGUwKCJzdWIiLCBpZCwgIl9NRkhEIikpJE1GSERkZXB0aCAtLT4NCjwhLS0gICB0IDwtIGdldChwYXN0ZTAoInN1YiIsIGlkLCAiX01GSEQiKSkkdEV4cCAtLT4NCg0KPCEtLSAgIGNhdCgiIyMjIiwgcGFzdGUwKCJTdWJqZWN0IiwgaWQpLCAiey19IiwnXG4nKSAtLT4NCjwhLS0gICBwbG90KHQsIGRlcCwgcGNoPTE2LCBjZXg9MSxjb2w9YyhyZXAoInJlZCIsIDUwMCksIHJlcCgiYmxhY2siLCBsZW5ndGgoZGVwKS01MDApKSkgLS0+DQo8IS0tICAgbGVnZW5kKCJ0b3ByaWdodCIsIGxlZ2VuZD1jKCJCYXNlbGluZSBkYXRhIiwgIk5ldyBkYXRhIiksIGNvbD1jKCJyZWQiLCAiYmxhY2siKSkgLS0+DQo8IS0tICAgY2F0KCdcbiBcbicpIC0tPg0KDQo8IS0tIH0gLS0+DQoNCjwhLS0gYGBgIC0tPg0KDQojIyBNRkhEIERlcHRoDQoNCkNhbGN1bGF0ZSBNRkhEIGRlcHRoLi4uDQoNCkV4cGxhaW4gc2luY2UgaXQgdGFrZSB2ZXJ5IGxvbmcgaXQgd2FzIHBlcmZvcm1lZCBvbiBzdXBlcmNvbXB1dGVyIGNsdXN0ZXIgaW4gcGFyYWxsZWwgYW5kIHRoZSBldmFsIG9wdGlvbiBpbiB0aGUgZm9sbG93aW5nIGNvZGUgY2h1bmsgd2FzIHNldCB0byBmYWxzZSBzaW5jZSB0aGlzIGNvdWxkIHRha2Ugd2Vla3MgdG8gcnVuIG9uIHRoZSBsb2NhbCBjb21wdXRlci4NCg0KYGBge3IgTUZIRC1kZXB0aCwgZXZhbD1GQUxTRX0NCg0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KbG9hZChmaWxlPSIuLi9EYXRhL3JEYXRhL3N1YkdzX2Zvcl9kZXB0aC5SZGF0YSIpDQoNCmNvcmVzID0gZGV0ZWN0Q29yZXMoKSAtIDIgIyB0byBnaXZlIHRoZSBzZXJ2ZXIgc29tZSBicmVhdGhpbmcgUm9vbQ0KY2wgPSBtYWtlUFNPQ0tjbHVzdGVyKGNvcmVzKQ0KcmVnaXN0ZXJEb1BhcmFsbGVsKGNsKQ0KDQpmb3IgKGlkIGluIHNldGRpZmYoMToxNSwgMTMpKSB7DQogIA0KICBhU2FnIDwtIGdldChwYXN0ZTAoInN1YiIsIGlkLCAiX2FNU0xUIikpJGFTYWcNCiAgYUxhdCA8LSBnZXQocGFzdGUwKCJzdWIiLCBpZCwgIl9hTVNMVCIpKSRhTGF0DQogIHRFeHAgPC0gZ2V0KHBhc3RlMCgic3ViIiwgaWQsICJfYU1TTFQiKSkkdGltZQ0KICANCiAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyBNb2RlIERlcHRoDQogIGluQ29udHJvbFNhZyA8LSBhU2FnWzE6NTAwLF0NCiAgaW5Db250cm9sTGF0IDwtIGFMYXRbMTo1MDAsXQ0KICBpbkNvbnRyb2xEZXB0aCA8LSB7TUZIRCh5MT1pbkNvbnRyb2xTYWcsIHkyPWluQ29udHJvbExhdCwgYWxwaGE9MC4xMjUsIEJldGE9MC41KX0kTUZIRGRlcHRoWzEsXQ0KICANCiAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyBmb3JlYWNoDQogIG9ubGluZURlcHRoIDwtIGMoKQ0KICBlbmQgPC0gbnJvdyhhU2FnKQ0KICBvbmxpbmVEZXB0aCA8LSBmb3JlYWNoKGk9NTAxOmVuZCwgLnBhY2thZ2VzID0gYygnZmRhLnVzYycsICd0aWR5dmVyc2UnLCAnTUZIRCcpLA0KICAgICAgICAgICAgICAgICAgICAgICAgIC5jb21iaW5lPSdjJykgJWRvcGFyJSB7DQogICAgICAgICAgICAgICAgICAgICAgICAgICB0ZW1wMSA8LSBhU2FnICU+JSAuW2ksXQ0KICAgICAgICAgICAgICAgICAgICAgICAgICAgdGVtcDIgPC0gYUxhdCAlPiUgLltpLF0NCiAgICAgICAgICAgICAgICAgICAgICAgICAgIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgYXBwZW5kMSA8LSByYmluZChpbkNvbnRyb2xTYWcsIHRlbXAxKQ0KICAgICAgICAgICAgICAgICAgICAgICAgICAgYXBwZW5kMiA8LSByYmluZChpbkNvbnRyb2xMYXQsIHRlbXAyKQ0KICAgICAgICAgICAgICAgICAgICAgICAgICAgDQogICAgICAgICAgICAgICAgICAgICAgICAgICB0ZW1wMyA8LSBNRkhEKHkxPWFwcGVuZDEsIHkyPWFwcGVuZDIsIGFscGhhPTAuMTI1LCBCZXRhPTAuNSkNCiAgICAgICAgICAgICAgICAgICAgICAgICAgIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgdGVtcDQgPC0gdGVtcDMkTUZIRGRlcHRoICU+JSAuWzEsNTAxXQ0KICAgICAgICAgICAgICAgICAgICAgICAgICAgdGVtcDQNCiAgICAgICAgICAgICAgICAgICAgICAgICB9DQogIA0KICBNRkhEZGVwdGggPC0gYyhpbkNvbnRyb2xEZXB0aCwgb25saW5lRGVwdGgpDQogIA0KICBhc3NpZ24ocGFzdGUwKCJzdWIiLCBpZCwgIl9NRkhEIiksDQogICAgICAgICBsaXN0KE1GSERkZXB0aD1NRkhEZGVwdGgsIHRFeHA9dEV4cCkpDQp9DQoNCnNhdmUoc3ViMV9NRkhELCBzdWIyX01GSEQsIHN1YjNfTUZIRCwgc3ViNF9NRkhELCBzdWI1X01GSEQsIHN1YjZfTUZIRCwgc3ViN19NRkhELCBzdWI4X01GSEQsDQogICAgIHN1YjlfTUZIRCwgc3ViMTBfTUZIRCwgc3ViMTFfTUZIRCwgc3ViMTJfTUZIRCwgc3ViMTRfTUZIRCwgc3ViMTVfTUZIRCwNCiAgICAgZmlsZT0iLi4vRGF0YS9yRGF0YS9NRkhELlJkYXRhIikNCg0KYGBgDQoNCiMjIFZpc3VhbGl6ZSB0aGUgTUZIRCBEZXB0aCB7LnRhYnNldCAudGFic2V0LWZhZGV9DQoNCmBgYHtyIHZpc19NRkhELCBmaWcuYWxpZ249ImNlbnRlciIsIHJlc3VsdHM9ImFzaXMiLCBvdXQud2lkdGg9IjEwMCUifQ0KDQpsb2FkKGZpbGU9Ii4uL0RhdGEvckRhdGEvTUZIRC5SZGF0YSIpDQoNCmZvciAoaWQgaW4gc2V0ZGlmZigxOjE1LCAxMykpIHsNCiAgZGVwIDwtIGdldChwYXN0ZTAoInN1YiIsIGlkLCAiX01GSEQiKSkkTUZIRGRlcHRoDQogIHQgPC0gZ2V0KHBhc3RlMCgic3ViIiwgaWQsICJfTUZIRCIpKSR0RXhwDQogIA0KICBjYXQoIiMjIyIsIHBhc3RlMCgiU3ViamVjdCIsIGlkKSwgInstfSIsJ1xuJykNCiAgcGxvdCh0LCBkZXAsIHBjaD0xNiwgY2V4PTEsY29sPWMocmVwKCJyZWQiLCA1MDApLCByZXAoImJsYWNrIiwgbGVuZ3RoKGRlcCktNTAwKSkpDQogIGxlZ2VuZCgidG9wcmlnaHQiLCBsZWdlbmQ9YygiQmFzZWxpbmUgZGF0YSIsICJOZXcgZGF0YSIpLCBjb2w9YygicmVkIiwgImJsYWNrIiksDQogICAgICAgICBwY2g9MTYpDQogIGNhdCgnXG4gXG4nKQ0KICANCn0NCg0KYGBgDQoNCg0KLS0tDQoNCiMgUmVmZXJlbmNlcyB7LX0NCg==